package 剑指offer;

public class Offer47_JZ {
    public static int maxValue(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        for(int i=0; i<rows; i++) {
            if(i == 0) {
                dp[i][0] = grid[i][0];
            }else {
                dp[i][0] = dp[i-1][0] + grid[i][0];
            }
        }
        for(int j=0; j<cols; j++) {
            if(j == 0) {
                dp[0][j] = grid[0][j];
            } else {
                dp[0][j] = grid[0][j] + dp[0][j-1];
            }
        }
        for(int row=1; row<rows; row++) {
            for(int col=1; col<cols; col++) {
                dp[row][col] = Math.max(grid[row][col]+dp[row-1][col], grid[row][col]+dp[row][col-1]);
            }
        }
        return dp[rows-1][cols-1];
    }

    public static void main(String[] args) {
//        int[][] arr = {{1, 3, 1},
//                {1, 5, 1},
//                {4, 2, 1}};
//        System.out.println(maxValue(arr));
        System.out.println(Integer.MAX_VALUE);
    }
}
